//https://leetcode.cn/problems/word-search/submissions/505145295/?envType=study-plan-v2&envId=top-100-liked

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

class Solution {
public:
    bool dfs(int cur_row,int cur_col,vector<vector<char>>& board,int s_index,std::string& word,vector<vector<bool>>&visited){
        int row=static_cast<int>(board.size());
        int col=static_cast<int>(board[0].size());

        if(cur_row<0||cur_row>=row || cur_col<0||cur_col>=col){
            return false;
        }
        if(visited[cur_row][cur_col]) {
            return false;
        }
        if(word[s_index]!=board[cur_row][cur_col]){
            return false;
        }
        if(s_index == word.size()-1){
            std::cout<< s_index<<std::endl;
            return true;
        }
        visited[cur_row][cur_col]=true;
        auto res1=dfs(cur_row-1,cur_col,board,s_index+1,word,visited);
        auto res2=dfs(cur_row,cur_col+1,board,s_index+1,word,visited);
        auto res3=dfs(cur_row+1,cur_col,board,s_index+1,word,visited);
        auto res4=dfs(cur_row,cur_col-1,board,s_index+1,word,visited);
        visited[cur_row][cur_col]=false;
        return res1||res2||res3||res4;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int row=static_cast<int>(board.size());
        if(row<1 || word.empty()) return false;
        int col=static_cast<int>(board[0].size());
        if(col<1) return false;
        vector<vector<bool>> visited(row,vector<bool>(col,false));
        
        for(int cur_row=0;cur_row<row;++cur_row){
            for(int cur_col=0;cur_col<col;++cur_col){
                if(dfs(cur_row,cur_col,board,0,word,visited)){
                    return true;
                }
            }
        }
        return false;
    }
};